package dfs_bfs.test279;

import org.junit.Test;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/8 11:05
 */
public class Solution1 {

    // BFS（有难度）
    public int numSquares(int n) {
        Queue<Integer> q = new LinkedList<>();
        q.add(0);
        int[] d = new int[n + 1];
        Arrays.fill(d, Integer.MAX_VALUE);
        d[0] = 0;
        while (!q.isEmpty()) {
            int c = q.poll();
            if (c == n) {
                return d[c];
            }
            for (int i = 1; i * i + c <= n; i++) {
                int j = i * i + c;
                if (d[j] > d[c] + 1) {
                    d[j] = d[c] + 1;
                    q.add(j);
                }
            }
        }
        return 0;
    }

    @Test
    public void test(){

        System.out.println(numSquares(13));
    }

}
